561. Array Partition

문제

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

예제 입출력

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:

1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
   So the maximum possible sum is 4.

참고

문제 전문은 여기에서 읽으실 수 있습니다.

풀이 1

접근법

1. 전체 수 중 큰 값들이 min 함수에서 살아남도록 하려면, 최대한 비슷한 값들끼리 묶어야 합니다. 따라서 정렬하는 것이 필연적입니다.
2. .sort() 가 sorted() 보다 더 빠릅니다.

구현 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

복잡도 분석

• $n$: 정수의 개수
• 시간복잡도: $O(n \log n)$
  • 정렬: $O(n \log n)$
  • 슬라이싱: $O(1)$
• 공간복잡도: $O(n)$

---

첵에 있는 풀이

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2

접근법: 오름차순으로 정렬

1. 숫자들을 배열에 추가하고 정렬합니다. (정렬이 필요한 이유는 풀이 1에서 설명)
2. 배열을 순회하면서 pair를 만들기 위해 임시 배열에 숫자를 추가합니다.
3. 임시 배열의 길이가 2가 되면, 최솟값을 전체 합에 더해줍니다.

구현 코드

from typing import List

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        pair = []
        nums.sort()

        for n in nums:
            pair.append(n)
            if len(pair) == 2:
                sum += min(pair)
                pair = []
        return sum

풀이 3

접근법: 짝수 번째 숫자들로 계산

1. 전체적인 사고 흐름은 풀이 1과 비슷합니다.
2. enumerate 로 배열을 순회하고, 인덱스가 짝수일 때 리턴 값에 더해줍니다. (짝수 번째 수가 pair에서 작은 값들이기 때문.)

구현 코드

from typing import List

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        nums.sort()

        for i, n in enumerate(nums):
            if i % 2 == 0:
                sum += n

        return sum

풀이 4

접근법: 파이썬 다운 풀이

1. 슬라이싱을 이용하면 전체 코드가 매우 간결합니다.
2. 또, 가장 빠른 풀이이기도 합니다.

구현 코드

from typing import List

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])